package J3_30;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class test {
    //给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
    public int longestOnes(int[] nums, int k) {
        int len = nums.length;
        int ret = -1;
        for (int l = 0, r = 0, zero = 0; r < len; r++) {
            if (nums[r] == 0) zero++;
            while (zero > k) {
                if (nums[l++] == 0) zero--;
            }
            ret = Math.max(ret, r - l + 1);
        }
        return ret;
    }


    //给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。
    //
    //如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。
    //
    //返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。
    //
    //数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。
    public int minimumAddedCoins(int[] coins, int target) {
        Arrays.sort(coins);
        int index = 0, x = 1, len = coins.length, ans = 0;
        while (x <= target) {
            if (index < len && coins[index] <= x) {
                x += coins[index];
                index++;
            } else {
                x *= 2;
                ans++;
            }
        }
        return ans;

    }
}
